This invention relates to packet data communications systems, and more particularly to methods of tracking sequence numbers used to identify message packets in communications systems.
In data communications networks, messages are usually split into small packets to conform to the communications protocol being used. For typical message traffic between digital processing stations in the network, an average-sized message may be split into a many packets, and this group of packets must be reassembled in the proper order at the receiving end. In addition, the receipt of all packets must be checked to see if any packets have been lost or duplicated in the transmission link. To keep track of the packets in such a system, the packets are assigned sequence numbers at some point at the transmitting end, either by the host computer or sending terminal, or by a protocol processor downstream of the host. At the receiving end, a processor must keep track of the sequence numbers and correlate incoming packet traffic by sequence numbers. The task is to keep track of sequence numbers in a large number space (e.g., a 32-bit sequence number) so that the actions(necessary to perform)associated with each sequence number are performed exactly once, in spite of duplicate or lost packets in the communications network.
There have been two basic alternatives for solving the problem of keeping track of sequence numbers in this environment. Both methods keep a base sequence number (baseSeq# as described below) similar to that discussed herein, but incremented in arbitrary units. The first alternative method keeps an ordered list for sequence numbers that arrive out-of-order. Whenever a new number arrives in order (i.e., matches the baseSeq#) the associated action is carried out and the baseSeq# is incremented, an operation which is quite efficient. However, if a sequence number arrives out of order because of network re-ordering or because a previous packet was lost, then the list must be scanned to detect duplicates and to insert the number in order in the list, an inefficient operation when a large number space is employed. Thus the amount of local processing at this step is very sensitive to the arrival order of the sequence numbers. This can very inefficient if re-ordering is common in the communications network. Also, the loop inherent in this method makes hardware implementation cumbersome.
The second prior method improves on the first alternative method by using hashing to reduce to a constant the average processing cost of the linear scan. Unfortunately, the worst case is still proportional to the maximum amount of out-of-orderliness. In addition, the worst case makes this method unsuitable for hardware implementation when insufficient buffering is available to absorb frequently occurring cases. If the cost of such buffering is significant or if guarantees have to be made that the buffering will not overflow, then the methods as described herein are clearly superior to all methods which have inferior worst case performance.
Thus, the prior methods of keeping track of sequence numbers in packet data communications systems have required an undue amount of processing by a receiver, or have required additional hardware in the form of buffering to a degree not otherwise needed. It is an objective to reduce the hardware burden and/or the processing burden, yet allow fast and reliable bookkeeping for sequence numbers.